Giga Games 1/Giga Games.iso/net/go/comp/mfg

Text File | 1993-06-20 | 22.3 KB | 533 lines

    Knowledge Representation in The Many Faces of Go

            David Fotland

            4863 Capistrano Ave
            San Jose Ca 95129
            [e-mail]

            February 27, 1993


Abstract:

This paper describes the representations of Go knowledge in The Many
Faces of GO, a strong computer Go program.  Knowledge is encoded in the
algorithms that recognize low level features, in the data structures
that describe the current position, and in patterns that are used to
suggest plausible moves.

1. Introduction

The Many Faces of Go is one of the strongest Go programs commercially
available.  It won the United States Computer Go competitions in
1988, 1991, and 1992, and is ranked 13 kyu in the USA.  It is based on
traditional AI techniques, such as alpha-beta search, rule based expert
systems, and pattern matching.  The go playing algorithm is about 30K
lines of 'C', plus a pattern database and a joseki database, and was
written by one person, part time, over a 10 year period.  As a
commercial program, it has about another 20K lines of code in user
interfaces for the IBM-PC, X windows, and PenPoint.

Go is a much more difficult AI problem than Chess, and must be attacked
with a knowledge intensive approach rather than brute force search.

2. Go is harder than Chess

There are several reasons why Go is a more difficult problem than Chess.
Strong chess programs depend on full width search 7 or more moves deep.
This is not possible in Go since a Go position is much more difficult to
evaluate than a chess position.  An accurate evaluation of a Go position must do
life and death analysis and assign a value for relative thickness and territory.  Just
Determining the location of secure territory is a difficult problem.  A chess
evaluation is dominated by the values of the pieces remaining on the board,
which is easy to get right.  If a go program misreads a life and death fight
there would be a large error in the evaluation score.  This leads to an
evaluation function for a go program that is orders of magnitude slower than
the chess evaluation function.  Where a PC chess program can examine 100,000
positions each move, Many Faces examines less than 100 positions before
deciding on a move.

Second, Go has many more legal plays than Chess at each move.  Even if the
evaluation functions were the same speed, the go program could not look as
many moves ahead.

Third, people read deeper in Go than in Chess.  A strong chess player might
read 10 moves ahead, but a strong Go player routinely reads much deeper.
This is because the board does not change as much after a move in go as it
does in chess, so it is easier for a person to visualize the board many moves
ahead.  Even a beginner can read 60 moves deep in a ladder that crosses the
board.

3. Knowledge in The Many Faces of Go

Go knowledge is incorporated into Many Faces of Go in 5 major areas.
First, there is low level go knowledge built into the evaluation, and
hard coded in 'C' 'if' statements.  This is knowledge used to determine
connectivity, eyes, potential eyes, and territory, as well as the move
generators and move sorters used by the tactician.  The general
philosophy here is to classify first, then analyze.  This makes the code
easier to debug.

Second, there is the dynamic knowledge stored about the state of the
current position.  This data is stored in a global database, and is
built up in successive passes, from low levels to high levels of abstraction.

Third, there is a rule based expert system with about 200 rules that
suggests plausible moves for full board evaluation.  I try to only
suggest reasonable moves for evaluation, to reduce the likelihood that
errors in the evaluation function will cause the program to play
terrible moves.

Fourth, there is a Joseki database of standard corner patterns,
currently consisting of over 36,000 moves, including all moves from most
of the joseki books published by Ishi Press.

Fifth, there is a pattern database of 8x8 patterns, each with a move
tree attached, currently with over 700 patterns and over 4,000 moves.

4. Program Components

The dynamic data stored about a position falls into 3 levels.  First is
incremental data, used for low level local data, such as
point_empty_neighbors, or string_liberties.  These data structures are
modified incrementally and adjusted as each stone is added to or removed
from the board.  Second, there is data that is recalculated as needed.  After a
move or sequence of moves, the area of the board affected by the move(s)
is recalculated, and areas that are not effected maintain their old
values.  This is used for connection strength, eyes, and string tactics.
Third, there is data that is recalculated for the entire board after a move or
sequence of moves.  These include group strength and radiated influence.

The dynamic data consists of:

Point environment
    which string is this point part of (or None)
    lists of adjacent Black and White strings
    list of adjacent empty points
    number of adjacent Black, White, and empty points
    list of connections
    which eye is this point part of
    White and Black influence
    ...
String data
    color
    list of points (stones) in string
    number of liberties
    list of liberty points of string
    list of adjacent enemy strings
    tactical status (captured, threatened, OK)
    list of connections
    which group is this string part of
    ...
Connection data
    two strings
    lists of points in connection
    number of connections
    type of connection
    strength of connection
Eye data
    list of points in eye
    list of vital points
    type of eye
    number of eyes
Group data
    list of strings in group
    list of eyes in group
    number of eyes in group
    group strength
    list of potential eyes
    lists of running points
    list of adjacent enemy groups
Territory
Score

Incremental data structures are modified as moves are made and taken
back.  Other data structures are maintained by the evaluation function.

EVALUATION FUNCTION

I have described the evaluation function elsewhere.  Its major
components are the tactical analyzer, which reads a single string with
the twin goals of removing it from the board, or making 5 liberties or
two eyes; the connection evaluator; the eye evaluator; the group
strength evaluator; and the territory evaluator.  It assigns a score to
the position, using Chinese style counting, where each point on the
board can have a value between +1 and -1, depending on how strongly it
is controlled by white or black.  Evaluation is a multiple pass process.

STRATEGY

Before each move, a strategy function looks at the dynamic data and
attempts to focus attention on the important areas of the board.  It
decides what phase the game is in.  Fuseki lasts as long as there are
corners that still contain unplayed joseki moves.  The game is in
Endgame if more that 120 moves have been played and all groups are
stable.  Otherwise the game is in the Middle Game.  It is possible for
the phase of the game to go back and forth from endgame to middle game.
The phase of the game is used as a qualifier for some of the move
generation moves.  For example the fill_dame rule will not fire unless
the phase is the endgame.

Strategy determines the relative score, and classifies it as "way
ahead" (over 40 points), "ahead" (20-40 points), "about even", "behind"
(over 10 points), and "way behind (over 20 points)".  This is also used
to qualify move generation rules.  For example if the program is way
ahead, it will play extra moves to be certain of big captures.  If
it is way behind it will try unsound invasions.

The strategy function determines the value of taking sente.  This declines
from 7 points at the start of the game to 1 point at move 220 and above.  At
the end of a full board lookahead and quiescence search, this value is added
to the side with sente, since presumably it can get that many points with a
big move somewhere.  Seven points is used at the start of the game since
internally the program uses Chinese style counting, which increases the value
of a move by one point relative to Japanese counting, and the value of the
first move is known to be about 5 1/2 points with Japanese counting.

It also finds friendly groups that urgently need defending.  These are
cutting groups and big groups.

It finds enemy groups that urgently need capturing.  These are big
groups, cutting groups, and groups adjacent to groups that urgently need
defending.

Attack and defense of groups marked urgent, and moves marked urgent by
the pattern matcher, are examined first, and if a reasonable urgent move
is discovered, no other moves are considered.

FULL BOARD LOOKAHEAD

Sequences for full board lookahead are provided directly from the Joseki
and Pattern databases.  Joseki variations are laid out on the board and
evaluated at the endpoints.  This allows the program to pick joseki that
it understands and that work well with adjacent corners.  Patterns also
suggest move sequences that are evaluated at the endpoints.

Move generators examine the group types, eye potentials, and running
points to generate move sequences to kill or save groups, fight semeai,
and run out to the center.

A rule based system generates other reasonable moves, such as
extensions, moyo expansion, etc.


QUIESCENCE SEARCH

Since the evaluation function ultimately reduces the position to a
single number, the score in 50ths of points, it is only accurate in a
quiet position.  It generates moves to save unsettled friendly groups or
kill unfriendly enemy groups, and calls itself recursively until it
finds a quiet position.  For contact fights, a special set of "obvious
local answer" patterns suggests moves that quiet the position.

5. Dynamic Data

CONNECTIONS

Each connection structure records all connectivity between a pair of
strings.  A connection point is a liberty of one string that sees a
stone of another string along a straight line, either 1, 2, or 3 points
away.  This suffices to discover hane, one point jump, knight moves, 2
point jumps, large knight moves, and 3 points jumps.  It does not see
double kosumi or watari played on the 1st line from two stones on the
second line.  These are handled by special case patterns.  A low level
incremental data structure that records the distance to the nearest
stone in each direction at each point makes it easy to incrementally
maintain the basic connections.  The structure looks like:

string s1, s2;        // two string numbers
int num_d1;        // number of distance one connections
int num_d2;        // number of distance 2 connections
int num_d3;        // number of distance 3 connections
list_t d1points;    // list of distance one connection points
list_t d2points;    // list of distance 2 connection points
list_t d3points;    // list of distance 3 connections
int type;        // type of connection:
                // hane
                // one point jump
                // half knight's move
                // knight's move
                // two point jump
                // half large knight's move
                // large knight's move
                // 3 point jump
                // multiple
int strength;        // strength of the connection
                // Already cut
                // Cuttable
                // Shared connection
                // Connected with aji
                // Connected solidly

Type and strength are recalculated as needed.  The others are incremental.
Each point maintains a list of connection structures that it appears in,
and each string maintains a list of connection structures that it
appears in.  The connection analysis code (representing low level go
knowledge coded directly in 'C') is about 1500 lines.

EYES

Each eye structure records information about a single block of empty
points completely or partially surrounded by stones of the same color,
or a tactically captured string.

list_t points;    // empty points in the eye
list_t vital;    // vital points for the eye, destroy it or finish it
int type;    // type of the eye
            // single point
            // two point
            // line eye (closed, open one end, open both ends)
            // big eye
            // dead group eye
int color;    // color of the eye
int min_eyes;    // number of eyes if opponent moves twice
int typ_eyes;    // number of eyes if opponent moves first
int max_eyes;    // number of eyes if I move first

The number of eyes is stored using the value 8 for one eye, 4 for 1/2
eye, etc.  Each point can be part of only one eye, and which eye is
recorded with the other data about a point.  All parts of the eye
structure are recalculated as needed.  Eye analysis is about 2400 lines
of 'C'.  There are a lot more patterns to recognize for eyes than for
connections, and nothing is incremental, so if I had to do it over again
I would make it pattern based rather than coded in 'C'.

POTENTIAL EYES

Each group has a list of potential eye structures, and lists of running
points.  These are used to evaluate group strength and to generate
attacking/defending moves.  A potential eye contains a value, location,
and type.  Types are:

Extend along the edge
    value is number of new points of eye space
    location is liberty to extend from
Play vital point to make an eye
    value is number of new eyes
    location is vital point
Connect to another group
    value is number of eyes
    location is connection number
Capture tactically threatened string
    value is number of eyes
    location is string number
Defend undercut territory on the edge
    value is number of new points for eye space
    location is liberty being undercut

Running points are recorded in several lists, by type, depending on
whether running this direction is toward friendly or enemy stones, etc.

Potential eyes and running points are reevaluated on the whole board at
each evaluation, consuming about 7% of the program's time.

INFLUENCE FUNCTION

An influence function is used that radiates from each stone with an
initial value that is dependent on the group strength, and falls off as
one over the distance.  Radiated values are summed independently at each
point for black and white.  Influence does not radiate through a stone
or a connection.  The influence is used to calculate territory and
thickness, find the best gradient for running moves, and help generate
moyo building or reducing/invading moves.  Influence is not used to
determine group connectivity.

A function that falls off as 1/distance will create a constant field inside
any fully enclosed area, no matter how big it is, which is desirable
for estimating territory.  Dead stones radiate negative influence.

6. Rule Based System For Move Suggestion

The move suggestion experts are:

Fuseki
    Playing in empty corner
    Shimari and kakari
    Joseki moves
Big moves on edge
    Towards enemy
    Invasions
    Between friendly stones
Playing in the center (reducing moves and junction lines)
Playing safe when ahead
    Respond when enemy adds stone to dead group
    Add extra stone to kill big group that is probably dead
Squirming around when behind
    Make a bogus invasion
    Try to make a hopeless group live
Pattern matching
    patterns for cutting and connecting
    patterns for surrounding and avoiding getting surrounded
    patterns for invasion and defending against invasion
    endgame patterns
    killing/saving groups patterns
    Shape moves
Saving a weak group
    making eyes
    running
    fighting semeais
Save threatened string
Capture threatened string
Killing a weak group
    surrounding
    taking eyes
Cutting and connecting
Contact fights
    Blocking
    extending for liberties
    hane
Ko threats
    make a big atari
Filling dame

The move suggestion code is easily extensible by adding more patterns or
firing rules based on other criteria.  The program has text associated with
each rule so it can "explain" its reasons for making moves.  This makes it
easier to debug.

7. Joseki Database

The Joseki database is stored as a directed acyclic graph of moves, with
the root representing an empty corner.  Transpositions are built into the
database manually as data is entered.  An uncompressed representation is
maintained in an ASCII file.  Each uncompressed node contains:

X and Y relative to corner (1-16 each)
Sibling pointer
First child pointer
Type: Urgent, normal, complex, trick, bad, ignore, ...
flags: color, symmetric, color reverse

Urgent moves take priority over any other
Complex and trick moves are avoided by the computer unless it is behind.
Bad moves are never played by the computer, but are in the database so
it can respond correctly if an opponent plays them.
Ignore is used to delete an erroneous entry in the database.

Color indicates whether the current move is the same color or opposite color
as the first move in the corner.  Symmetric indicates that this move
makes the corner symmetric again.  Color reverse is needed for some
transpositions, for example certain 3-4 joseki are 5-3 joseki transposed with
colors reversed.

A compressed representation is used directly by the program.
(x,y) are reduced to 6 bits via a lookup table.  Values 0-62 index the
lookup table of the 62 most common x,y pairs.  Value 63 escapes to the
next byte which contains the full x,y pair.  Sibling and child pointers
are replaced by two bits, has_sibling, and has_child.  Data is stored in
depth first order, except where lines converge due to a transposition,
when a full 2 byte pointer is stored.  Most entries are 1 byte long.  The
longest possible entry is 5 bytes.  Across the entire database, the
average move is stored in 1.2 bytes.

8. Pattern Database

There is a pattern matcher with over 500 patterns in it.  Each pattern is
8x8, where each point is specified as black, white, empty, don't care,
white or empty, black or empty, or black or white.  Each pattern has
a set of attributes with it that must also match.  For example, "the
stone at (4,2) must be alive", or "the stone at (2,5) must have at least
2 liberties".  Each pattern has a move tree attached that is used for
full board lookahead.

Patterns are also used for reading obvious local sequences based on shape.

Internally a pattern is stored as three 8 byte arrays, one for black points,
one for white, and one for empty.  For example a black point in the
pattern is indicated by setting the appropriate bit in the black array.
Black or Empty is indicated by setting bits in both the black and empty
arrays.  Don't care is indicated by setting corresponding bits in all 3
arrays.  Each pattern needs to be matched at each point on the board, in
8 orientations, and with colors reversed.  Rather than rotate the
patterns, I rotate the board before comparing.  Color reversal is handled
by reversing the black and white arrays.  Once I have 3 arrays extracted
from the board for a particular position, the pattern match is simple.
Just bitwise AND the corresponding Black, white, and empty arrays; bitwise
OR the three results, and if the result is all ones, then there is a match.

After I find a matching pattern I check that the attributes specified by
the pattern match.

I plan to have at least 1000 patterns, so performance is an issue.  1000
patterns compared at 361 locations at 16 orientations is over 5
million comparisons.  A full comparison requires 24 byte ANDS, 16 byte
ORS, and 8 compares, or 48 primitive operations.  That's almost 300
million operations to determine which patterns match at a single board
position.

I use an 8 bit hash function to reduce the number of patterns examined.
Of course since there are don't cares in the patterns, a pattern may appear
on more than one hash chain (current average is 3 chains).  The hash
reduces the number of patterns examined by about a factor of 20.  I
remember which patterns match from move to move and only rematch in the
area near the last move.  This reduces the number of points where patterns
need to be matched from 361 to about 50.  I do the bitwise operations
32 bits at a time, and most patterns miscompare on the first word, which
reduces the number of logical operations about 6 on average.  This reduces
the number of operations to match all patterns down to about 350,000.
This is still slow enough that I only match all the patterns once
each time the computer has to make a move, to find sequences to read.  A
small subset of the patterns is used for obvious local lookahead during
the quiescence search.  The program currently spends about 1.5% of its time
matching patterns.

9. Knowledge acquisition

A graphical joseki editor allows me to enter about 400 new moves an hour,
and compiles the database to the compressed binary form that the program
uses.

A graphical pattern editor allows easy modification of the patterns
or move trees and can display 36 patterns at a time.

The program can play through a professional game and compare its choices to
the pro's.  When it didn't even consider the pro's move, it cuts out
the pattern from the pro's game and saves it.  This turned out to be much
less useful that I expected, since many of these moves involved difficult
fights, where an 8x8 pattern was not big enough, or where the proper move
was selected based on deep reading, not the local stone pattern.


10. Debugging Aids

Many of the data structures are incremental.  I can optionally include code
that periodically recalculates the incremental data structures from scratch
and verifies that they are correct.  This code also walks all of the
lists and finds any memory leaks.  I'm confident that the program contains
no bugs in incremental updates or memory leaks.

Some data values are only recalculated as needed.  Sometimes an eye or
a tactical lookahead needs to be recalculated, and it doesn't get noticed.
To detect bugs here I can include code that evaluates each position twice,
before and after lookahead.  A difference indicates that something wasn't
reevaluated.  There are many situations that can cause missed reevaluations.
In test games they come up about once in 1000 moves.  These are not critical
bugs since they mimic similar oversights that people make, but I fix them
as I find them.

The debugging version of the program can dump all of the internal data
structures in an easy to read form.  When the program makes a bad move I
can quickly determine the cause.

I run two kinds of regression tests.  First, I run about 100 self play games
at different levels and handicaps with all the checking code included.
Second, I have about 400 problems from Graded Go Problems For Beginners,
and the program can automatically play thru them to produce a report of
which problems got the wrong answers.

I wrote an interface between Many Faces of Go and the Internet Go Server
so Many Faces can play games there unattended.  I collect some of these
test games as samples that I can examine in detail to fix the problems
that lead to bad moves.

11. Summary

Playing the game of Go well is a difficult AI problem.  Because of the
large board and difficult evaluation, large searches are impractical,
and a knowledge intensive approach is required.  Many Faces encodes
local, low level knowledge in C algorithms for speed, and higher level
pattern knowledge in databases optimized for size.